long long powMod(long long a, long long b, long long mod) {
    long long result = 1;
    a = a % mod; // 先对a取模
    while (b > 0) {
        if (b % 2 == 1) { // 如果b是奇数
            result = (result * a) % mod;
        }
        a = (a * a) % mod; // 平方a并取模
        b /= 2; // 将b减半
    }
    return result;
}